//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
import java.util.ArrayList;
import java.util.List;
//Definition for a binary tree node.
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) {
         this.val = val;
     }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);

        return list;
    }
    public int findKthLevelCount(int k,TreeNode root){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return findKthLevelCount(k -1,root.left) + findKthLevelCount(k -1,root.left);

    }

    public TreeNode findVal(TreeNode root, int val){
        if(root == null){
            return null;
        }
        if( root.val == val){
            return root;
        }
        TreeNode left = findVal(root.left,val);
        if(root.left != null){

            return left;
        }
        TreeNode right = findVal(root.right,val);
        if(root.right != null){

            return right;
        }
        return null;
    }

}


public class Test {
}
